package com.gyg.程序员面试金典;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 面试题 02.06. 回文链表
 * 编写一个函数，检查输入的链表是否是回文的.
 */
public class T02_06 {

    public static void main(String[] args) {
        T02_06 t02_06 = new T02_06();
//        boolean palindrome2 = t02_06.isPalindrome2();
//        System.out.println(palindrome2);
    }

    /**
     * 使用Stack堆栈
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode node1 = head;
        ListNode node2 = head;
//        定义一个堆栈缓冲区，存放head中的所有元素
        Stack<Integer> stackBuffer = new Stack<Integer>();
//        将链表中的元素压入栈中，先入栈的在栈底，后入栈的在栈顶
        while (node1 != null) {
            stackBuffer.push(node1.val);
            node1 = node1.next;
        }
//        遍历链表，此时出栈的元素的顺序是链表的逆序，
        while (node2 != null) {
//            如果是回文的，那么逆序和正序应该是一样的，如果不一样就说明不是回文的
            if (node2.val != stackBuffer.peek()) {
                return false;
            } else {
//                如果当前出栈元素和对应的链表中的数据一样，就将当前栈顶元素出栈，下次循环判断下一个出栈元素
//                栈顶元素出栈
                stackBuffer.pop();
                node2 = node2.next;
            }
        }
        return true;
    }

    /**
     * 使用Linkedlist队列实现
     *
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
//        （1）判断如果是一个空串或者长度只有1，直接就是回文数
        if (head == null || head.next == null){
            return true;
        }
//        （2）借助列表来存储前半部分的数
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        ListNode slowNode = head;
        ListNode fastNode = head;
//        （3）将前半部分的数放置到列表中
        while (fastNode != null && fastNode.next != null) {
            linkedList.addLast(slowNode.val);
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
//        过滤奇数和偶数
//        （4）如果快指针指向的最后一个元素，则说明是奇数的链表，慢指针下移
        if (fastNode != null && fastNode.next == null){
//            将慢指针指向后半部分链表的第一个
            slowNode = slowNode.next;
        }

//        （5）将前半部分链表与后半部分链表比较
        while (slowNode != null) {
//            将列表中的存放着的前半部分链表的数据依次从后往前出队列，返回队列最后一个元素并删除这个元素
//            linkedlist是双向链表
            if (linkedList.pollLast() != slowNode.val) {
                return false;
            }
            slowNode = slowNode.next;
        }
        return true;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
